9月快到了,要開始準備一些資料,湊30天用,所以除非有一篇Rails幼幼班的資料,不然不會單獨分享解題了。
不是因為K-pop的MV不夠用了

Factorial Trailing Zeroes

題目連結:https://leetcode.com/problems/factorial-trailing-zeroes/
題目重點:降冪,"!"號是啥。

5! = 5*4*3*2*1 = 120

題目整理

# @param {Integer} n
# @return {Integer}
def trailing_zeroes(n)

end

p trailing_zeroes(3)  #=>0
p trailing_zeroes(5)  #=>1
p trailing_zeroes(0)  #=>0

如果不清楚對數,我們先看以下資訊

2.7.3 :001 > 5*4*3*2*1
 => 120 
2.7.3 :002 > 3*2*1
 => 6 

乘號按到煩了
寫個程式吧

2.7.3 :007 > (1..5).to_a.reduce(:*)
 => 120 
2.7.3 :008 > (1..10).to_a.reduce(:*)
 => 3628800 
2.7.3 :009 > (1..15).to_a.reduce(:*)
 => 1307674368000 
2.7.3 :010 > (1..20).to_a.reduce(:*)
 => 2432902008176640000 
2.7.3 :011 > (1..25).to_a.reduce(:*)
 => 15511210043330985984000000 
 
#自己找出:*是啥,這件事對菜鳥而言,真的很重要。

如果,想直接運用reduce算出結果,然後由後往前算有幾個零,這樣解是沒有錯的,但是leetcode上會告訴你,太浪費時間了,直接噴錯。

我沒有試過,真的!

先找出為何結果會有0

[1, 2, 3, 4, 5] = 120 , 2 * 5 出現 10. 
#代表算式中如果有一組2與5,就會有一個0

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] = 3628800 
#最後一個數字10 = 2 * 5, 兩組[2, 5]了, 兩個零

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] = 1307674368000 
#15有一個5,一堆偶數有2,湊三組[2, 5]了,三個零。
#另外發現一件事,2數量一定超過5的數量。

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] = 2432902008176640000
#20,第四組[2, 5],所以其實我們要找出5的數量,就會有幾個零。

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25] = 15511210043330985984000000 
#6個零,因為25 = 5 * 5,25是特別數,有兩個5。 4 + 2 = 6

接著我們看一下怎麼找出幾個5

#5,10,15,20都比較單純。直接除即可
2.7.3 :019 > 5/5
 => 1 
2.7.3 :020 > 10/5
 => 2 
2.7.3 :021 > 15/5
 => 3 
2.7.3 :022 > 20/5
 => 4 
 
#25
2.7.3 :023 > 25/5
 => 5
#商數為大於等於5時,需在除一次
2.7.3 :024 > 5/5
 => 1 
#5 + 1 = 6

所以

 5的次數 += n/5
 n /= 5

不放心我們再用菜鳥方法,請電腦告訴我們是否正確

2.7.3 :025 > (1..45).to_a.reduce(:*)
 => 119622220865480194561963161495657715064383733760000000000 
#10個零
2.7.3 :026 > 45/5
 => 9 
2.7.3 :027 > 8/5
 => 1 
#9+1 = 10

2.7.3 :030 > (1..75).to_a.reduce(:*)
 => 24809140811395398091946477116594033660926243886570122837795894512655842677572867409443815424000000000000000000 
#眼睛快花了...18個零
2.7.3 :031 > 75/5
 => 15 
2.7.3 :032 > 15/5
 => 3 

跑迴圈吧!

跑n/5的迴圈,不是n!的迭代!

def trailing_zeroes(n)
  five_count = 0
  while n > 0
    five_count += n/5
    n /= 5
  end
  five_count
end

#由於如果(小於5的數/5)商數是0,所以不用寫額外判斷n是否為0的編碼了。

大神的one line

def trailing_zeroes(n)
  n == 0 ? 0 : n/5 + trailing_zeroes(n/5)
  #or
  n > 0 ? n/5 + trailing_zeroes(n/5) :0
end
  
#翻成中文不一樣,邏輯結果一樣...

語法補充

2.7.3 :033 > 10.zero?
 => false 
2.7.3 :034 > 0.zero?
 => true 
2.7.3 :036 > (15/5).zero?
 => false 
2.7.3 :037 > (3/5).zero?
 => true 
 
(n/5).zero? ? 0 : n/5 + trailing_zeroes(n/5)
#其實這寫法比較好理解